package com.redstar.day06_pingfanggen;

/**
 * 在不使用 sqrt(x) 函数的情况下，得到X的平方根正整数的部分
 *
 * @author lihongxing
 * @date 2021/05/12 22:27
 */
public class Test {


    public static void main(String[] args) {
        int num = 1000000;
        double sqrt = Math.sqrt(num);
        System.out.println("sqrt：" + sqrt);
        System.out.println("+++++++++++++++");
        System.out.println("暴力法：" + violence(num));
        System.out.println("+++++++++++++++");
        System.out.println("二分法：" + binarySearch(num));

    }

    /**
     * 暴力破解
     * 当一个数 i*i<x 且 (i+1)*(i+1)>=x 时，说明x的平方根就在这之间，后面只需要确认是 X 还是 X+1 就行。
     */
    private static int violence(int x) {
        if (x < 0) {
            return -1;
        }
        if (x == 0) {
            return 0;
        }
        int product = 0;
        int j = 0;
        //此处判断也可以写成：int i = 0; i <= x / 2; i++
        for (int i = 0; i < (x / 2 )+ 1; i++) {
            j++;
            product = i + 1;
            if (product * product == x) {
                System.out.println("暴力法循环了"+j+"次");
                return product;
            }
            if (i * i < x && product * product > x) {
                System.out.println("暴力法循环了"+j+"次");
                return i;
            }
        }
        System.out.println("暴力法循环了"+j+"次");
        return -1;
    }

    /**
     * 二分法：
     * 不断的将左边界或者右边界向中间靠拢，并且将边界内的中间值与目标值比较，
     * 直到中间值与目标值相等或者左右边界重合则停止查找。
     */
    private static long binarySearch(long x) {
        if (x < 0) {
            return -1;
        }
        long left = 0,right = x;
        long mid = -1;
        /**注意，此处不能使用 mid = (left + right ) / 2  来计算中间值，有内存溢出的风险*/
        //开始遍历
        int i= 0;
        while (left <= right) {
            ++i;
            mid = left + (right - left) / 2;
            if (mid * mid > x) {
                right = mid;
            } else if (mid * mid < x) {
                left = mid;
                if (left + 1 == right) {
                    System.out.println("二分法循环了"+i+"次");
                    return left;
                }
            } else {
                System.out.println("二分法循环了"+i+"次");
                return mid;
            }
        }
        System.out.println("二分法循环了"+i+"次");
        return mid;
    }


    /**
     * 牛顿迭代
     */
    private static int newton(int x) {

        return -1;
    }


}
